This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
To generate so-called Rivest-Shamir-Adleman (RSA) moduli for use in public cryptography one may proceed as follows.
Let N=pq be the product of two large primes. Let e and d denote a pair of public and private exponents, satisfyinged≡1(mod λ(N)),with gcd(e, λ(N))=1 and λ being Carmichael's function. As N=pq, we have λ(N)=1 cm(p−1, q−1). Given x<N, the public operation (e.g., message encryption or signature verification) consists in raising x to the e-th power modulo N, i.e., in computing y=xe mod N. Then, given y, the corresponding private operation (e.g., decryption of a ciphertext or signature generation) consists in computing yd mod N. From the definition of e and d, we obviously have that yd≡x (mod N). The private operation can be carried out at higher speed through Chinese remaindering (CRT mode). Computations are independently performed modulo p and q and then recombined. In this case, private parameters are {p, q, dp, dq, iq} withdp=d mod(p−1),dq=d mod(q−1), andiq=q−1 mod p. 
We then obtain yd mod N asCRT(xp, xq)=xq+q[iq(xp−xq)mod p]where xp=ydp mod p and xq=ydq mod q.
In summary, a RSA modulus N=pq is the product of two large prime numbers p and q, satisfying gcd(λ(N), e)=1. If n denotes the bit-size of N then, for some 1<n0<n, p must lie in the range [2n−n0−1/2, 2n−n0−1] and q in the range [2n0−1/2, 2n0−1] so that 2n−1<N=pq<2n. For security reasons, so-called balanced moduli, with n=2n0, are generally preferred.
Typical present-day RSA moduli range in length from 1024 to 4096 bits, and it has become customary for applications to require moduli of at least 2048 bits. However, there are still programs and/or devices running the RSA-enabled applications that are designed to support only 1024-bit moduli.
It will be appreciated a solution that enables the compression moduli so that they can fit in shorter buffers or bandwidths would be greatly beneficial. Rather than storing/sending the whole RSA moduli, a lossless compressed representation is used. This also solves compatibility problems between different releases of programs and/or devices. In addition, such techniques can be used for improved efficiency: savings in memory and/or bandwidth.
One such solution is described by Vanstone and Zuccherato in “Short RSA Keys and Their Generation”, Journal of Cryptology, New York, N.Y., US, vol. 8, no. 8, 1995, pages 101-114, XP000853671. The solution enables specification of up to N/2 leading bits, but it is rather complicated, requiring e.g. factorization of the number given by the specified bits. In addition, the resulting moduli are relatively easy to factor.
Another such solution is described by Lenstra, Arjen K. in “Generating RSA moduli with a predetermined portion”; Advances in Cryptology—ASIACRYPT '98, volume 1514 of Lecture Notes in Computer Science, pp. 1-10; Springer 1998. This solution is an improvement upon the solution by Vanstone and Zuccherato as it is less complicated and as the resulting moduli are more difficult to factor.
However, neither of the prior art methods allow the predetermination of more than half of the bits of an RSA modulus.
The present invention, however, improves on Lenstra's generation method in that it for example allows greater compression.